// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-31 14:32
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetcodeRepeat;

import java.util.List;

/**
 * 线段树
 * 1 线段树属性：
 * fileds + node + merger
 * 2 查询
 * 3 更新
 * 4 线段树更像是一个索引，而不是存储数据的容器
 */
@SuppressWarnings("ALL")
public class SegmentTree<E> {

    /**
     * 属性值
     */
    private Node[] data;
    private Merger<E> merger;
    // 原数据大小
    private int size;

    public SegmentTree(E[] source, Merger<E> merger) {
        this.merger = merger;
        this.size = source.length;
        this.data = new Node[4 * size];
        buildTree(0, source, 0, size - 1);
    }

    /**
     * 线段树节点
     */
    class Node<E> {
        E value;
        int left, right;

        public E getValue() {
            return value;
        }

        public void setValue(E value) {
            this.value = value;
        }

        public int getLeft() {
            return left;
        }

        public void setLeft(int left) {
            this.left = left;
        }

        public int getRight() {
            return right;
        }

        public void setRight(int right) {
            this.right = right;
        }

        public Node(E value, int left, int right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 线段树节点更新 -> 方法嵌套方法
     * 数据节点更新的时候除了叶子节点其他节点也需要进行更新
     */
    public void update(int Index, E value) {
        update(0, Index, value);
    }

    public void update(int treeIndex, int index, E value) {
        Node treeNode = data[treeIndex];
        int left = treeNode.left, right = treeNode.right;
        if (left == right) {
            treeNode.setValue(value);
            return;
        }
        int leftTreeIndex = leftChild(treeIndex), rightTreeIndex = rightChild(treeIndex);
        int middle = leftTreeIndex + ((rightTreeIndex - leftTreeIndex) >> 1);
        if (middle < index) {
            update(rightTreeIndex, index, value);
        } else {
            update(leftTreeIndex, index, value);
        }
        treeNode.setValue(merger.merge(elementData(leftTreeIndex), elementData(rightTreeIndex)));
    }


    /**
     * 线段树查询操作,可以实现区域查询，单点查询
     * 当left == right的时候实现的就是单点查询,当left < right的时候实现的就是区域查询
     * 单点查询的结果就是查询节点的value值，区域查询就是查询线段树对应节点索引所有的数据节点在merge之和的数据集合
     */
    public E search(int queryLeft, int queryRight) {
        if (queryLeft < 0 || queryLeft > queryRight || queryLeft > size - 1 || queryRight > size - 1 || queryRight > size) {
            throw new IllegalArgumentException("Index is illegle");
        }
        return search(0, queryLeft, queryRight);
    }


    private E search(int treeIndex, int queryLeft, int queryRight) {
        // treeIndex 的传入是为实现树的递归查找
        Node treeNode = data[treeIndex];
        int left = treeNode.left, right = treeNode.right;
        if (left == queryLeft && right == queryRight) {
            return elementData(treeIndex);
        }
        // 线段树默认是一棵二叉树，只是左孩子和右孩子节点的关系是通过堆式存储的，没有明示
        int treeLeftIndex = leftChild(treeIndex), treeRightIndex = rightChild(treeIndex);
        int middle = left + ((right - left) >> 1);
        if (queryLeft > middle) {
            return search(treeRightIndex, queryLeft, queryRight);
        } else if (queryRight <= middle) {
            return search(treeLeftIndex, queryLeft, queryRight);
        } else {
            // 查询的区间不是完全在当前线段树节点的左区间或者右区间
            E leftTreeEle = search(treeLeftIndex, queryLeft, middle);
            E rightTreeEle = search(treeRightIndex, middle + 1, queryRight);
            return merger.merge(leftTreeEle, rightTreeEle);
        }
    }


    /**
     * buildTree:线段树构造
     * 叶子节点和非叶子节点的值不一样,指定树节点，传入构造的数据集source[left] - source[right]
     *
     * @param treeIndex: 传入当前树的根节点
     * @param source:    原数据数组
     * @param left:      线段树左边界
     * @param right:     线段树右边界
     */
    public void buildTree(int treeIndex, E[] source, int left, int right) {
        // 原数据数组只有一个值
        if (left == right) {
            data[treeIndex] = new Node(source[left], left, right);
            return;
        }
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        int middle = left + ((right - left) >> 1);
        buildTree(leftTreeIndex, source, left, middle);
        buildTree(rightTreeIndex, source, middle + 1, right);
        E treeData = merger.merge(elementData(leftTreeIndex), elementData(rightTreeIndex));
        data[treeIndex] = new Node(treeData, left, right);
    }

    /**
     * 包装获取孩子节点方法
     * 返回孩子节点的索引
     */
    int leftChild(int index) {
        return index * 2 + 1;
    }

    int rightChild(int index) {
        return index * 2 + 2;
    }

    /**
     * 包装获取节点值的方法
     */
    E elementData(int index) {
        return (E) data[index].value;
    }

    /**
     * 数据整合接口
     */
    interface Merger<E> {
        E merge(E a, E b);
    }


    /**
     * 使用线段树解决最繁忙服务器问题
     * 1 merge方法
     * 2 查询什么？
     */
//    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
//        int n = arrival.length;
//        SegmentTree<Integer> segmentTree = new SegmentTree<>(n, (a, b) -> {
//            return Math.max(a, b);
//        });
//        for (int i = 0; i < n; i++) {
//
//        }
//    }
}
